package com.cat.DataStructure04;

import java.awt.geom.Area;
import java.util.*;

/**
*   @description https://leetcode.cn/problems/bus-routes/
*   @author 曲大人的喵
*   @create 2025/11/30 16:13
*   @since JDK17
*/

public class Solution28 {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        int n = routes.length, ans = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (var x : routes[i]) {
                map.computeIfAbsent(x, y -> new ArrayList<>()).add(i);
            }
        }
        if (target == source) {
            return 0;
        }
        if (!map.containsKey(source) || !map.containsKey(target)) {
            return -1;
        }
        List<Integer> q = new ArrayList<>();
        Set<Integer> h = new HashSet<>();
        q.add(source);
        h.add(source);
        while (!q.isEmpty()) {
            var t = q;
            q = new ArrayList<>();
            ans++;
            for (int x : t) {   //
                for (int y : map.get(x)) {
                    if (routes[y] != null) {
                        for (int k : routes[y]) {   //
                            if (k == target) {
                                return ans;
                            }
                            if (h.add(k)) {
                                q.add(k);
                            }
                        }
                        routes[y] = null;
                    }
                }
            }
        }

        return -1;
    }
}
